// splay
// https://www.luogu.com.cn/problem/P3369
// https://www.luogu.com.cn/problem/P3391
// https://soj.turingedu.cn/problem/60301/

int tsiz, root;
struct Node {
    int val, siz;
} dat[maxn];
int tag[maxn];
int ch[maxn][2], fa[maxn];

int n, q;

inline int new_node(int v) {
    dat[++tsiz] = {v, 1};
    return tsiz;
}

inline void pushup(int now) {
    dat[now].siz = dat[ch[now][0]].siz + dat[ch[now][1]].siz + 1;
}

inline void pushdown(int now) {
    if (tag[now]) {
        swap(ch[now][0], ch[now][1]);
        tag[ch[now][0]] ^= 1, tag[ch[now][1]] ^= 1;
        tag[now] = 0;
    }
}

void rotate(int now) {
    int father = fa[now], grand = fa[father], d = (now == ch[fa[now]][0]);
    ch[father][d ^ 1] = ch[now][d], fa[ch[now][d]] = father, pushup(father);
    ch[now][d] = father, fa[father] = now, pushup(now);
    fa[now] = grand;
    if (grand) ch[grand][father == ch[grand][1]] = now, pushup(grand);
    // if (grand) ch[grand][ch_type(father)] = now, pushup(grand); // fa[father] 已经被修改了，调用 ch_type 将导致错误
}

int splay(int now, int top = 0) {
    if (now == 0) return 0; // 草
    while (fa[now] != top) {
        int father = fa[now];
        if (fa[father] != top) rotate((now == ch[father][1]) ^ (father == ch[fa[father]][1]) ? now : father);
        rotate(now);
    }
    if (top == 0) root = now;
    return now;
}

void insert(int v) {
    int now = root, father = 0;
    while (now) {
        pushdown(now);
        father = now, now = ch[now][v > dat[now].val];
    }
    now = new_node(v), fa[now] = father;
    if (father) ch[father][v > dat[father].val] = now;
    splay(now);
}

int find(int v) {
    int now = root, father = 0;
    while (now) {
        pushdown(now);
        if (v == dat[now].val) return splay(now);
        father = now, now = ch[now][v > dat[now].val];
    }
    splay(father);
    return 0;
}

void erase(int v) {
    if (find(v) == 0) return;
    if (ch[root][0] == 0 || ch[root][1] == 0) {
        root = ch[root][0] | ch[root][1], fa[root] = 0;
        return;
    }
    int d = (dat[ch[root][0]].siz > dat[ch[root][1]].siz); // 大的子树作新根，splay 以减高度
    int now = ch[root][d ^ 1];
    while (ch[now][d]) {
        pushdown(now);
        now = ch[now][d];
    }
    splay(now, root);
    fa[ch[root][d]] = now, ch[now][d] = ch[root][d], pushup(now);
    root = now, fa[root] = 0;
}

int get_rank(int v) { // return inf for no find
    int now = root, father = 0, lsiz = 0;
    while (now) {
        pushdown(now);
        if (v > dat[now].val) lsiz += dat[ch[now][0]].siz + 1;
        father = now, now = ch[now][v > dat[now].val];
    }
    splay(father);
    return lsiz + 1;
}

int get_val(int rk) {
    int now = root, father = 0;
    while (now) {
        pushdown(now);
        int now_rk = dat[ch[now][0]].siz + 1;
        if (rk == now_rk) return dat[splay(now)].val; // find
        father = now, now = ch[now][rk > now_rk];
        if (rk > now_rk) rk -= now_rk;
    }
    splay(father);
    return 0;
}

int get_pre(int v, int top = root) {
    int now = top, father = fa[top], back = -inf;
    while (now) {
        pushdown(now);
        if (v > dat[now].val) back = max(back, dat[now].val);
        father = now, now = ch[now][v > dat[now].val];
    }
    splay(father);
    return back;
}

int get_nex(int v, int top = root) {
    int now = top, father = fa[top], back = inf;
    while (now) {
        pushdown(now);
        if (v < dat[now].val) back = min(back, dat[now].val);
        father = now, now = ch[now][v >= dat[now].val];
    }
    splay(father);
    return back;
}

void show(int now, int dep = 1) {
    if (now == 0) return;
    pushdown(now);
    show(ch[now][0], dep + 1);
    printf("%d ", dat[now].val - 1);
    // printf("val: %d, siz: %d, dep = %d\n", dat[now].val, dat[now].siz, dep);
    show(ch[now][1], dep + 1);
}

void reverse(int l, int r) {
    int u = get_val(l - 1), v = get_val(r + 1);
    splay(v), splay(u, v);
    if (ch[u][1]) tag[ch[u][1]] ^= 1;
}
